The present invention generally pertains to data processing systems and is particularly directed to an improvement in last-in-first-out (LIFO) stacks.
A stack is used in a data processing system to temporarily store data. A LIFO stack is one in which data is stored by "pushing" the data into the stack from the top, and in which data is retrieved by "popping" data out of the stack from the top. The operation of adding data to the stack is referred to as a "push"; and the operation of retrieving data from the stack is referred to as a "pop".
Stacks are usually implemented in data processing systems as virtual stacks through the use of random access memories (RAM's) addressed by up/down counters. This is done by programming the data processing system to maintain the up/down counter in a register and then using the register to index the stack's base address. Very large virtual stacks can be realized in this way. However, the penalty paid for this is speed. A push or a pop requires both a register increment and an indexed memory access, not to mention the instruction fetch cycle. A slower, but more common scheme is to store a stack pointer in the topmost data storage cell of the address space reserved for the stack. This scheme requires three memory cycles, one to increment the stack pointer, one to store the incremented pointer, and one to access the data storage cell.